package Algorithm.jianzhi;

public class Jian04 {

//    二维数组中的查找
//    在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//    时间复杂度：O(nm)。二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小。
//    空间复杂度：O(1)。

//暴力
    public boolean find1(int[][] matrix,int target){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int rows=matrix.length,columns=matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j]==target) {
                    return true;
                }
            }
        }
        return false;
    }
//线性查找

//    时间复杂度：O(n+m)O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。
//    空间复杂度：O(1)O(1)。

public boolean find2(int[][] matrix,int target) {
    if (matrix==null||matrix.length==0||matrix[0].length==0) {
        return false;
    }
    int rows=matrix.length,columns= matrix.length;
    int row=0,column=columns-1;
    while (row<rows && column >= 0) {
        int num =matrix[row][column];
        if (num==target) {
            return true;
        }
        else if (num > target) {
            column--;
        }else {
            rows++;
        }
    }
        return false;
}


}
